package collectionsUtils;

import pojo.User;

import java.util.*;

/**
 * 功能描述: 并查集结构,合并与查询两个元素是否属于同一集合的问题 频繁调用的时候, 时间复杂度O(1), 用来处理两个集合之间的问题
 *      如果是按值传递,String 或者基本数据类型,是可以支持的
 *      如果是引用传递,则需要重写equals和hashCode方法,否则无法找到要操作的元素
 *
 *      1. 集合去重,
 *      2. 在一个集合绝对连通的情况下, 判断两个元素是否属于同一个集合 list.get(0) 与遍历
 * 2024/05/18
 * <p>
 * ZhangYi
 */
public class MyUnionSet {

    /**
     * 功能描述: 内部操作的时候,必须依赖于这个否则UnionSet就找不到要操作的元素
     * 2024/05/18
     * <p>
     * ZhangYi
     */
    public static class Node<V> {
        V val;

        public Node(V val) {
            this.val = val;
        }
    }

    public static class UnionSet<V> {
        private Map<V, Node<V>> nodeMap;
        private Map<Node<V>, Node<V>> parentNodeMap;
        private Map<Node<V>, Integer> sizeNodeMap;

        public UnionSet(List<V> nodeList) {
            this.nodeMap = nodeMap = new HashMap<>();
            this.parentNodeMap = new HashMap<>();
            this.sizeNodeMap = new HashMap<>();

            for (V v : nodeList) {
                Node<V> vNode = new Node<>(v);
                nodeMap.put(v,
                            vNode);
                parentNodeMap.put(vNode,
                                  vNode);
                sizeNodeMap.put(vNode,
                                1);
            }
        }

        /**
         * 功能描述:获取去重后的集合
         *
         * @return int
         *
         *
        */
        public int getSize(){
            return sizeNodeMap.size();
        }
        /**
         * 功能描述: 合并两个节点, 如果两个节点的父节点不同,则进行合并
         *
         * @param a
         * @param b
         */
        public void union(V a,
                          V b) {
            // 如果节点a,或者节点b 不存在就不需要进行union操作
            if (!nodeMap.containsKey(a) || !nodeMap.containsKey(b)) {
                return;
            }

            Node<V> aNode = nodeMap.get(a);
            Node<V> bNode = nodeMap.get(b);
            // 查询父节点
            Node<V> aParentNode = findParent(aNode);
            Node<V> bParentNode = findParent(bNode);
            // 如果父节点不同,则进行合并
            if (aParentNode != bParentNode) {
                Integer asize = sizeNodeMap.get(aParentNode);
                Integer bsize = sizeNodeMap.get(bParentNode);
                if (asize > bsize) { // 说明a 为大节点,b节点挂到a节点下
                    parentNodeMap.put(bNode,aNode);
                    sizeNodeMap.put(aParentNode,asize+bsize); // 这里维护的一定是a节点的父节点,所以这里要删除b节点的父节点
                    sizeNodeMap.remove(bParentNode);
                }else {
                    parentNodeMap.put(aNode,bNode);
                    sizeNodeMap.put(bParentNode,asize+bsize); // 这里维护的一定是b节点的父节点,所以这里要删除a节点的父节点
                    sizeNodeMap.remove(aParentNode);
                }
            }
        }

        /**
         * 功能描述: 判断两个节点是否在同一个集合中
         *
         * @param a
         * @param b
         * @return boolean
         */
        public boolean isSameSet(V a,
                                V b) {
            // 如果节点a,或者节点b 不存在就不需要进行union操作
            if (!nodeMap.containsKey(a) || !nodeMap.containsKey(b)) {
                return false;
            }
            return findParent(nodeMap.get(a)) == findParent(nodeMap.get(b));
        }
        /**
         * 功能描述: 返回父节点, 同时进行一个扁平化的操作, O(1)的关键 ,union与 isSameSet 都会触发这里的操作
         *
         * @param aNode
         * @return {@link Node }<{@link V }>
         */
        private Node<V> findParent(Node<V> aNode) {
            Node<V> vNode = parentNodeMap.get(aNode);
            Stack<Node<V>> nodeStack = new Stack<>(); // 在找父节点的时候,经过的所有路径节点
            while (vNode != aNode){
                nodeStack.push(vNode);
                aNode = vNode;
                vNode = parentNodeMap.get(aNode);
            }
            // 弹栈,进行扁平化的从操作
            while (!nodeStack.isEmpty()){
                parentNodeMap.put(nodeStack.pop(),vNode);
            }
            return vNode;
        }
    }


    public static void main(String[] args) {
        List<User> userList= new ArrayList<>();
        for (int i = 0; i < 3; i++) {
            userList.add(new User(String.valueOf(i), "zhangsan"+String.valueOf(i)));
        }

        UnionSet<User> userUnionSet = new UnionSet<>(userList);
        for (int i = 1; i < userList.size(); i++) {
            userUnionSet.union(userList.get(i-1),userList.get(i));
        }

        System.out.println(1);
        System.out.println(userUnionSet.isSameSet(userList.get(0),
                                                  new User("5",
                                                           "zhangsan1")));
    }
}
